package 左哥算法.ch04桶排序;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Ch04桶排序 {

    /**
     * 桶排序(基数排序)：
     * 先准备十个桶，分别是0-9
     * 将个位放入对应桶中
     */
    @Test
    public void testRadix() {
        int[] nums = {2, 1, 3, 4, 5, 7, 5, 9, 6,-5};    //不能排负数
        radixSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void radixSort(int[] nums) {
        int max=nums[0];
        for (int i = 1; i < nums.length; i++) {
            max=nums[i]>max?nums[i]:max;
        }
        Queue<Integer>[] queues = new Queue[10];
        Arrays.setAll(queues,v->new LinkedList<Integer>());    //填充queues
        int y=1;
        while ((max/=y)>0){     //对每个进位进行遍历
            y*=10;
            for (int i = 0; i <nums.length; i++) {
                queues[Math.abs(nums[i]%y)].add(nums[i]);     //入桶
            }
            int i=0;
            for (Queue<Integer> queue : queues) {
                while (!queue.isEmpty()) {
                    nums[i++]= queue.poll();        //出桶
                }
            }
        }
    }

}
